import java.util.*;

//public class SlidingPuzzle implements Cloneable, State {
public class SlidingPuzzle implements State, Cloneable{
	/**
	 * An enumeration representing the four possible actions of the sliding
	 * block puzzle.
	 */
	public enum Action {
		UP,
		DOWN,
		LEFT,
		RIGHT
	}

	private int size;
	private int[] state;
	private int emptyRow, emptyCol;
	
	//private int cost;
	

	/**
	 * Initializes a new <code>SlidingPuzzle</code> object representing
	 * a 3x3 puzzle in the solved configuration.
	 */
	public SlidingPuzzle() {
		this(3);
	}

	/**
	 * Initializes a new <code>SlidingPuzzle</code> object representing
	 * a <code>size</code> by <code>size</code> puzzle in the solved
	 * configuration.
	 * 
	 * @param size The width and height of the puzzle.
	 */
	public SlidingPuzzle(int size) {
		if (size < 1)
			throw new IllegalArgumentException();

		this.size = size;
		state = new int[size * size];
		for (int i = 0; i < size * size; i++)
			state[i] = i;
	}

	/**
	 * Initializes a new <code>SlidingPuzzle</code> object representing
	 * a puzzle with the specified configuration.  The size of the puzzle is
	 * floor(sqrt(<code>state.length</code>)), i.e., the largest puzzle that
	 * is fully specified by <code>state</code>.  
	 *  
	 * @param state The configuration of the puzzle in row-major order.
	 * @throws IllegalArugmentException If the configuration contains illegal
	 * or duplicate tiles.
	 */
	public SlidingPuzzle(int[] state) {
		size = (int)Math.sqrt(state.length);
		if (size < 1)
			throw new IllegalArgumentException();

		for (int i = 0; i < size * size; i++) {
			if (state[i] < 0 || state[i] >= size * size) // enforce numbers 0 to size
				throw new IllegalArgumentException();
			for (int j = 0; j < i; j++) // enforce no duplicate numbers
				if (state[i] == state[j])
					throw new IllegalArgumentException();
		}
		this.state = new int[size * size];
		for (int i = 0; i < size * size; i++) {
			this.state[i] = state[i]; // copy from provided state to this objects state variable
			if (state[i] == 0) {
				emptyRow = i / size;
				emptyCol = i % size;
			}
		}
	}

	/**
	 * Modifies this <code>SlidingPuzzle</code> to represent a random
	 * puzzle configuration of the same size.  Warning: may produce a puzzle
	 * that cannot be solved.
	 */
	public void randomize() {
		ArrayList<Integer> tmp = new ArrayList<Integer>(state.length);
		for (int i : state)
			tmp.add(i);
		Collections.shuffle(tmp);
		for (int i = 0; i < tmp.size(); i++) {
			state[i] = tmp.get(i);
			if (state[i] == 0) {
				emptyRow = i / size;
				emptyCol = i % size;
			}
		}
	}

	/**
	 * Returns the size of the puzzle represented by this
	 * <code>SlidingPuzzle</code>.  The size of the puzzle is its width and
	 * height.
	 * 
	 * @return The size of this <code>SlidingPuzzle</code>.
	 */
	public int getSize() {
		return size;
	}

	/**
	 * Returns the tile at a specified location in this
	 * <code>SlidingPuzzle</code>.
	 *  
	 * @param row A row within this <code>SlidingPuzzle</code>.
	 * @param col A column within this <code>SlidingPuzzle</code>.
	 * @return The tile at the specified location, an integer in the range
	 * 0 to <code>getSize()</code> * <code>getSize()</code> - 1. 
	 */
	public int getTile(int row, int col) {
		if (row < 0 || row >= size || col < 0 || col >= size)
			throw new IllegalArgumentException();
		
		return state[row * size + col];
	}

	/**
	 * Indicates whether the specified action is legal for the current
	 * configuration of this <code>SlidingPuzzle</code>.
	 * 
	 * @param a An action from the enumeration {@link Action}.
	 * @return <code>true</code> if the action is legal, or
	 * <code>false</code> otherwise.
	 */
	public boolean canPerformAction(Action a) {
		switch (a) {
			case UP:	return canPerformUP();
			case DOWN:	return canPerformDOWN();
			case LEFT:	return canPerformLEFT();
			case RIGHT:	return canPerformRIGHT();
			default:	return false;
		}
	}

	/**
	 * Indicates whether the {@link Action#UP UP} action is legal for the
	 * current configuration of this <code>SlidingPuzzle</code>.
	 * 
	 * @return <code>true</code> if the {@link Action#UP UP} action is legal,
	 * or <code>false</code> otherwise.
	 */
	public boolean canPerformUP() {
		return emptyRow != size - 1;
	}

	/**
	 * Indicates whether the {@link Action#DOWN DOWN} action is legal for the
	 * current configuration of this <code>SlidingPuzzle</code>.
	 * 
	 * @return <code>true</code> if the {@link Action#DOWN DOWN} action is
	 * legal, or <code>false</code> otherwise.
	 */
	public boolean canPerformDOWN() {
		return emptyRow != 0;
	}

	/**
	 * Indicates whether the {@link Action#LEFT LEFT} action is legal for the
	 * current configuration of this <code>SlidingPuzzle</code>.
	 * 
	 * @return <code>true</code> if the {@link Action#LEFT LEFT} action is
	 * legal, or <code>false</code> otherwise.
	 */
	public boolean canPerformLEFT() {
			return emptyCol != size - 1;
	}

	/**
	 * Indicates whether the {@link Action#RIGHT RIGHT} action is legal for the
	 * current configuration of this <code>SlidingPuzzle</code>.
	 * 
	 * @return <code>true</code> if the {@link Action#RIGHT RIGHT} action is
	 * legal, or <code>false</code> otherwise.
	 */
	public boolean canPerformRIGHT() {
			return emptyCol != 0;
	}

	/**
	 * Returns the set of actions that are legal for the current configuration
	 * of this <code>SlidingPuzzle</code>.
	 * 
	 * @return A {@link Set} of legal actions from the enumeration {@link
	 * Action}.
	 */
	public Set<Action> getAvailableActions() {
		EnumSet<Action> actions = EnumSet.noneOf(Action.class);
		for (Action a : Action.values())
			if (canPerformAction(a))
				actions.add(a);
		return actions;
	}

	/**
	 * Modifies this <code>SlidingPuzzle</code> to reflect performing the
	 * specified action.
	 * 
	 * @param a An action from the enumeration {@link Action}.
	 * @throws IllegalStateException If the specified action is not legal for
	 * the current configuration of this <code>SlidingPuzzle</code>.
	 */
	public void performAction(Action a) {
		switch (a) {
			case UP:	performUP();	break;
			case DOWN:	performDOWN();	break;
			case LEFT:	performLEFT();	break;
			case RIGHT:	performRIGHT();	break;
		}
	}

	/**
	 * Modifies this <code>SlidingPuzzle</code> to reflect performing the
	 * {@link Action#UP UP} action.
	 * 
	 * @throws IllegalStateException If the {@link Action#UP UP} action is
	 * not legal for the current configuration of this
	 * <code>SlidingPuzzle</code>.
	 */
	public void performUP() {
		if (!canPerformUP())
			throw new IllegalStateException();

		state[emptyRow * size + emptyCol] = state[(emptyRow+1) * size + emptyCol];
		state[++emptyRow * size + emptyCol] = 0;
	}

	/**
	 * Modifies this <code>SlidingPuzzle</code> to reflect performing the
	 * {@link Action#DOWN DOWN} action.
	 * 
	 * @throws IllegalStateException If the {@link Action#DOWN DOWN} action is
	 * not legal for the current configuration of this
	 * <code>SlidingPuzzle</code>.
	 */
	public void performDOWN() {
		if (!canPerformDOWN())
			throw new IllegalStateException();

		state[emptyRow * size + emptyCol] = state[(emptyRow-1) * size + emptyCol];
		state[--emptyRow * size + emptyCol] = 0;
	}

	/**
	 * Modifies this <code>SlidingPuzzle</code> to reflect performing the
	 * {@link Action#LEFT LEFT} action.
	 * 
	 * @throws IllegalStateException If the {@link Action#LEFT LEFT} action is
	 * not legal for the current configuration of this
	 * <code>SlidingPuzzle</code>.
	 */
	public void performLEFT() {
		if (!canPerformLEFT())
			throw new IllegalStateException();

		state[emptyRow * size + emptyCol] = state[emptyRow * size + emptyCol + 1];
		state[emptyRow * size + ++emptyCol] = 0;
	}

	/**
	 * Modifies this <code>SlidingPuzzle</code> to reflect performing the
	 * {@link Action#RIGHT RIGHT} action.
	 * 
	 * @throws IllegalStateException If the {@link Action#RIGHT RIGHT} action
	 * is not legal for the current configuration of this
	 * <code>SlidingPuzzle</code>.
	 */
	public void performRIGHT() {
		if (!canPerformRIGHT())
			throw new IllegalStateException();

		state[emptyRow * size + emptyCol] = state[emptyRow * size + emptyCol - 1];
		state[emptyRow * size + --emptyCol] = 0;
	}

	/**
	 * Returns a string representation of this <code>SlidingPuzzle</code>.
	 * 
	 * @return A string representation of this <code>SlidingPuzzle</code>.
	 */
	public String toString() {
		StringBuilder sb = new StringBuilder();
		int width = ("" + (size * size - 1)).length();
		String format = " %" + width + "d";
		for (int i = 0; i < size * size; i++) {
			if (state[i] != 0)
					sb.append(String.format(format, state[i]));
				else
					sb.append(String.format(" %" + width + "c", ' '));
			if ((i + 1) % size == 0)
				sb.append('\n');
		}
		return sb.toString();
	}

	/**
	 * Indicates whether this <code>SlidingPuzzle</code> object is equal to
	 * another object.  A <code>SlidingPuzzle</code> object is equal to another
	 * object if and only if that object is a <code>SlidingPuzzle</code> of the
	 * same size and configuration as this <code>SlidingPuzzle</code> object.
	 * 
	 * @param obj The object with which to compare this
	 * <code>SlidingPuzzle</code> object. 
	 * @return <code>true</code> if this <code>SlidingPuzzle</code> is equal to
	 * the specified object, or <code>false</code> otherwise. 
	 */
	public boolean equals(Object obj) {
		if (!(obj instanceof SlidingPuzzle))
			return false;
		if (obj == this)
			return true;
		return Arrays.equals(state, ((SlidingPuzzle)obj).state);
	}

	/**
	 * Returns a hash code value for this <code>SlidingPuzzle</code>, based on
	 * its current configuration.
	 * 
	 * @return A hash code value for this <code>SlidingPuzzle</code>.
	 */
	public int hashCode() {
		return Arrays.hashCode(state);
	}

	
	 
	 /** TODO is this really used?
	  *  Used by compareTo T
	  * @return The state of this slidingPuzzle instance.
	  */
	 public int[] getState()
	 {
		 return this.state;
	 }
	/**
	 * Creates and returns an independent copy of this <code>SlidingPuzzle</code>.
	 * 
	 * @return An independent copy of this <code>SlidingPuzzle</code>.
	 */
	public SlidingPuzzle clone() {
		try {
			SlidingPuzzle copy = (SlidingPuzzle)super.clone();
			copy.state = (int[])state.clone();
			return copy;
		} catch (CloneNotSupportedException e) {
			System.out.println(e.getStackTrace());
		}
		return null;
	}

/*	Used for slidingPuzzle that implements State, replaced for version that
 * use StateWithCost
 **/	
	public Iterable<State> getNeighbors() {
		ArrayList<State> neighbors = new ArrayList<>(4);
		for (Action a : getAvailableActions()) {
			SlidingPuzzle neighbor = clone();
			neighbor.performAction(a);
			neighbors.add(neighbor);
		}
		return neighbors;
	}
}